
#define MAX(a, b) ((a > b)? a: b)

typedef struct operacion {
	int id;
	int costo;
	int r; //tam del camino mas largo hasta ella desde el inicio
	int t; //tam del camino mas largo desde ella hasta el fin
	int maquina; //maquina a la que pertenece la operacion
	struct operacion *pj;
	struct operacion *sj;
	struct operacion *pm;
	struct operacion *sm;
} operacion;

/* Lee el archivo de una instancia e inicializa todas las estructuras
 * Parametros:
 *		archivo: nombre del archivo de la instancia
 * Valor de retorno:
 *		1 si el archivo no existe o si el formato del archivo no es valido
 *		-1 si no hay suficiente memoria disponible
 *		0 en otro caso
 */
int leer_instancia (char *);

/* Elimina un elemento de un arreglo de enteros
 * Parametros:
 *		arr: el arreglo donde se va a eliminar el elemento
 *		tam: longitud del arreglo arr
 *		elem: elemento del arreglo que se quiere eliminar
 */
void quitar(int *, int, int);

/* Heuristica que selecciona la proxima operacion a planificar
 * Parametros:
 *		arr: arreglo de operaciones candidatas a ser planificadas
 *		tam: longitud del arreglo arr
 * Valor de retorno:
 *		operacion seleccionada para ser planificada
 */
int mejor_operacion(int *, int);

/* Algoritmo list-schedule que genera una solucion inicial de manera greedy
 * Parametros:
 *		prim_cad_maq: arreglo de operaciones iniciales de cada maquina
 *		ult_cad_maq: arreglo de operaciones finales de cada maquina
 *      modalidad: entero que indica como es la solucion inicial.
 *                 Si el parametro es 0, la solucion es deterministica, en
 *                 otro caso, la solucion es aleatoria
 */
void solucion_naive(operacion **, operacion **, int);

/* Imprime una solucion
 * Parametros:
 *		solucion: matriz que representa una solucion y contiene por cada maquina,
 *                las operaciones en el orden que se realizan en ella
 *		comienzo: arreglo que contiene los tiempos de comienzo de cada operacion
 */
void imprimir_solucion (operacion ***, int *);

/* Calcula recursivamente el tiempo de comienzo mas temprano de la operacion op
 * Parametros:
 *		operaciones_est: arreglo de tiempos de comienzo mas temprano
 *						 de cada operacion
 *		op: operacion de la cual se esta calculando el tiempo
 * Valor de retorno:
 *		tiempo de comienzo mas temprano de la operacion op
 */
int calcular_r (int *, operacion *);

/* Calcula recursivamente el tiempo desde que termina la operacion op
 * hasta que finalizan todos los trabajos
 * Parametros:
 *		colas: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 *		op: operacion de la cual se esta calculando el tiempo
 * Valor de retorno:
 *		tiempo desde que termina la operacion op hasta que finalizan
 *		todos los trabajos
 */
int calcular_t(int *, operacion *);

/* Calcula el costo de una solucion, el tiempo de comienzo mas temprano
 * de cada operacion y el tiempo desde que termina cada operacion hasta
 * que finalizan todos los trabajos
 * Parametros:
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		ultimos: arreglo de operaciones finales de cada maquina
 *		operaciones_est: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		colas: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		tiempo desde que inicia la primera operacion hasta que finaliza la ultima operacion
 */
int costo_solucion (operacion **, operacion **, int *, int *);

/* Calcula los nodos que estan en el camino critico y
 * guarda el id de cada uno en un arreglo llamado nodos
 * Parametros:
 *		nodos: arreglo que contiene los id de las operaciones que se encuentran
 *			   en el camino critico
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		cantidad de operaciones del camino critico
 */
int camino_critico(int **, operacion **, int, int *, int *);

/* Calcula una cota inferior para el costo resultante de cambiar
 * el orden de las num_nodos operaciones que estan en el orden
 * actual[] en alguna maquina para que queden en el orden de 
 * acuerdo a nodos[].
 * Parametros:
 *		num_nodos: cantidad de operaciones que van a ser intercambiadas
 *		actual: arreglo que representa el orden actual en una maquina
 *				de las num_nodos operaciones
 *		nodos: arreglo que representa el orden despues del intercambio
 *			   en una maquina de las num_nodos operaciones
 *		r: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t: arreglo de tiempos desde que termina cada operacion hasta que
 *		   finalizan todos los trabajos
 * Valor de retorno:
 *		cota inferior del intercambio entre operaciones
 */
int lpath(int, operacion **, operacion **, int *, int *);

/* Para dos operaciones u,v consecutivas en la misma maquina, que ademas
 * son parte de un camino critico, halla cual es el mejor movimiento
 * que se puede hacer cambiandolos de orden, entre si y con sus sucesores
 * o predecesores
 * Parametros:
 *		u: operacion predecesora de la operacion v en una maquina x
 *		v: operacion sucesora de la operacion u en una maquina x
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el mejor movimiento de u y v
 *		mejor: arreglo que representa el orden de las operaciones
 *			   despues de ejecutar el mejor movimiento
 * Valor de retorno:
 *		cantidad de operaciones involucradas en el mejor movimiento
 */
int estim(operacion *, operacion *, operacion **, operacion **, int *, int *, int *);

/* Calcula el movimiento que se debe realizar para obtener el mejor vecino
 * segun la vecindad NA
 * Parametros:
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el mejor movimiento
 *		mejor: arreglo que representa el orden de las operaciones
 *			   despues de ejecutar el mejor movimiento
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		ultimos: arreglo de operaciones finales de cada maquina
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		-1 en caso de no encontrar algun vecino que no esta prohibido
 *		en otro caso, cantidad de operaciones involucradas en el mejor movimiento
 */
int mejor_movimiento_na (operacion **, operacion **, operacion **, operacion **, int, int *, int *);

/* Ejecuta el movimiento de las operaciones que se encuentran en el orden
 * representado por el arreglo actual para que queden en el orden representado
 * por el arreglo movimiento
 * Parametros:
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el movimiento
 *		movimiento: arreglo que representa el orden de las operaciones
 *					despues de ejecutar el movimiento
 *		tam_movimiento: cantidad de operaciones involucradas en el movimiento
 *		inicial: arreglo de operaciones iniciales de cada maquina
 *		final: arreglo de operaciones finales de cada maquina
 */
void hacer_movimiento (operacion **, operacion **, int, operacion **, operacion **);

/* Calcula el movimiento que se debe realizar para obtener el mejor vecino
 * segun la vecindad N1
 * Parametros:
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el mejor movimiento
 *		mejor: arreglo que representa el orden de las operaciones
 *			   despues de ejecutar el mejor movimiento
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		ultimos: arreglo de operaciones finales de cada maquina
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		-1 en caso de no encontrar algun vecino que no esta prohibido
 *		en otro caso, cantidad de operaciones involucradas en el mejor movimiento
 */
int mejor_movimiento_n1 (operacion **, operacion **, operacion **, operacion **, int, int *, int *);

/* Metaheuristica que mejora una solucion inicial haciendo busqueda local
 * y utilizando una estructura de memoria que describen las soluciones
 * visitadas
 * Parametros:
 *		mejor_vecindad: funcion que devuelve el mejor movimiento a realizar
 *						de acuerdo a una vecindad en particular
 *      modalidad: entero que indica como es la solucion inicial.
 *                 Si el parametro es 0, la solucion es deterministica, en
 *                 otro caso, la solucion es aleatoria
 *		taboo_size: longitud de la lista taboo
 */
void tabu_search (int (*)(), int, int);
